No. 013 (2024.1.9)
(Markdown 記法ではないので注意 → 記法 を参照すること) 前回
参加者
abap34 yuchi yamaguchi.icon あけましておめでとうございます
antimon2
(ここに参加した人が自分の名前 / ID を追記していく)
前回からの置き手紙
domtree 周り調べる？
メモ
domtree.jl によれば参考文献は
code:plaintext
# LG05 Linear-Time Algorithms for Dominators and Related Problems # Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
# ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
#
# LT79 A fast algorithm for finding dominators in a flowgraph # Thomas Lengauer, Robert Endre Tarjan, July 1979, ACM TOPLAS 1-1
#
# GI16 An Experimental Study of Dynamic Dominators # Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Federico
# Santaroni, April 2016
ChatGPT 謹製の冒頭コメントの翻訳
code:plaintext
このファイルでは、Georgiadisの博士論文 LG05 に記載されている Semi-NCA (SNCA) ドミネータツリー構築アルゴリズムを実装しています。このアルゴリズムは、Simple Lengauer-Tarjan (SLT) アルゴリズム LG79 を簡略化したもので、LLVMで採用されているアルゴリズムと一致し、実装の簡潔さと効率性のバランスが取れたものとされています。 また、このファイルでは、SNCAを拡張し、制御フローグラフ (CFG) におけるエッジの挿入および削除をサポートするドミネータツリーの更新アルゴリズムも実装しています。この拡張版は GI16 で Dynamic SNCA (DSNCA) として記載されており、全体的なパフォーマンスが最も高いとされる別のアルゴリズムである DBS ではなく、DSNCA が選ばれています。これは、DSNCA の方が理解と実装が容易であり、エッジ削除に対して良好に動作し、全体的なパフォーマンスがほぼ同等だからです。 SNCA はまずセミドミネータを計算し、その後、セミドミネータを基に直接ドミネータを計算します。ノードのセミドミネータは、そのノードへのセミドミネータパスが存在するノードのうち、最小のプレオーダー番号を持つノードです。セミドミネータパスとは、プレオーダー番号がパスの始点および終点を除いて、終点のプレオーダー番号より大きいノードからなるパスのことです。直感的には、セミドミネータは、DFS ツリー内のノードの祖先を避けつつ、CFG 上でルートにできるだけ近づくパスを取ることで、ノードの直接ドミネータを近似します。
セミドミネータを計算する際、SNCA はノードに非自明なセミドミネータ（DFSツリーの親以外のセミドミネータ）がある場合、「パス圧縮」を実行します。パス圧縮では、ノードの「ラベル」が伝播されます。このラベルは、そのノードを通過するセミドミネータパスに関連付けられたセミドミネータ候補を表します。
例えば、以下の CFG でパス圧縮が実行されます。DFS ツリーに含まれないエッジはアスタリスク (*) で示されています。ノードはプレオーダー番号でラベル付けされ、すべてのエッジは下向きです。
見れるところ
一旦真ん中を読むことにする
→ どうやって進めましょうね
次回
その他